/*
 * @lc app=leetcode.cn id=430 lang=javascript
 *
 * [430] 扁平化多级双向链表
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val,prev,next,child) {
 *    this.val = val;
 *    this.prev = prev;
 *    this.next = next;
 *    this.child = child;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
// 迭代版深度优先遍历
var flatten = function(head) {
  // 将有child节点的节点保存进栈
  const stack = []
  let current = head
  while (current) {
    if (current.child) {
      stack.push(current.next)
      current.next = current.child
      current.child.prev = current
      current.child = null
    }
    // child节点走到头了,拼接栈里面的节点
    if (!current.next && stack.length) {
      let next = stack.pop()
      if (next) {
        current.next = next
        next.prev = current
      } else {
        continue
      }
    }
    current = current.next
  }
  return head
};
// @lc code=end

// 深度优先遍历递归版
// var flatten = function(head) {
//   var dfs = (root) => {
//     // 保留当前处理child的尾节点
//     let last = null
//     let cur = root
//     while (cur) {
//       // 先处理child
//       if (cur.child) {
//         // 保存cur的next节点
//         let next = cur.next
//         // 得到child的尾部元素
//         let childLast = dfs(cur.child)
//         // 将节点next与child相连
//         cur.next = cur.child
//         cur.child.prev = cur
//         // 如果有next，拼接到child的尾节点
//         if (next) {
//           childLast.next = next
//           next.prev = childLast
//         }
//         // 将child置为空，以免重复处理
//         cur.child = null
//       } else {
//         last = cur
//       }
//       cur = cur.next
//     }
//     return last
//   }
//   dfs(head)
//   return head
// }

